package main.old.new_2023.last.month_6;

import java.util.*;

/**
 * @Description:
 * todo LCP 41. 黑白翻转棋
     * 在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。
     * 当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0620 {
    int m;
    int n;
    int sum = 0;

    public int flipChess(String[] chessboard) {
        m = chessboard.length;
        n = chessboard[0].length();
        //遍历， index 位置 从八个方向堵截白字，白字变黑之后加入队列，依次扩散，广度优先
        for (int i = 0; i < m;i++){
            for (int j = 0;j < n;j++){
                if (chessboard[i].charAt(j) == '.'){
                    //有空格才能落子
                    sum = Math.max(sum,wTob(i,j,chessboard));
                }
            }
        }
        return sum;
    }

    //广度优先-遍历查询
    private int wTob(int i,int j,String[] chessboard){
        int tempSum = 0;
        //转为String二维数组
        char[][] str = new char[m][n];
        for (int k =0;k < m;k++){
            str[k] = chessboard[k].toCharArray();
        }
        //队列，存放新变成黑子的坐标
        Deque<int[]> blackKeys = new ArrayDeque<>();
        blackKeys.push(new int[]{i, j});
        str[i][j] = 'X';
        while (!blackKeys.isEmpty()){
            int[] pop = blackKeys.pop();
            //落子位置
            int x = pop[0];
            int y = pop[1];
            for (int q=-1; q < 2 ;q++){
                for (int p = -1;p < 2;p++){
                    //跳过本身位置
                    if (q==0 && p ==0){
                        continue;
                    }
                    int curX = x + q;
                    int curY = y + p;
                    //有白子
                    while (curX >=0 && curY>=0 && curX<m && curY<n && str[curX][curY]=='O' ){
                        curX +=q;
                        curY +=p;
                    }
                    // 有黑棋包围：回退反转白棋、计数 以及 添加进队列
                    if (curX >= 0 && curY >= 0 && curX < m && curY < n && str[curX][curY] == 'X') {
                        curX -= q;
                        curY -= p;
                        // 这里是 || 不是 && 因为有可能是在横向或者垂直方向上走，这时候其中一个坐标是保持等于关系的
                        while (curX != x || curY != y) {
                            str[curX][curY]='X';
                            blackKeys.push(new int[]{curX, curY});
                            tempSum++;
                            curX -= q;
                            curY -= p;
                        }
                    }
                }
            }
        }
        return tempSum;
    }

    public static void main(String[] args) {
        String[] chessboard= {"....X.","....X.","XOOO..","......","......"};
        Solution0620 temp = new Solution0620();
        int s = temp.flipChess(chessboard);
        System.out.println(s);
    }
}
